package 数据结构和算法.链表;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.concurrent.ForkJoinPool;

/**
 * @author zls
 * @date 2022/8/30 10:44 下午
 */
public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
        ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }


    public static void main(String[] args) {
//        String s = minWindow("ADOBECODEBANC", "ABC");
//        System.err.println(s);
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.poll();
        ForkJoinPool forkJoinPool = new ForkJoinPool();
    }


    public static String minWindow(String s, String t) {
          // 初始化 needs 和 window
        Map<Character, Integer> needs = new HashMap<>(t.length());
        for(int i = 0; i < t.length(); i++) {
            Integer last = needs.getOrDefault(t.charAt(i), 0);
            needs.put(t.charAt(i), last + 1);
        }
        Map<Character, Integer> window = new HashMap<>(needs.size());
        needs.forEach((key, value) -> window.put(key, 0));
        int left = -1;
        int tempLeft = 0;
        while (tempLeft < s.length()) {
            if (needs.containsKey(s.charAt(tempLeft))) {
                left = tempLeft;
                break;
            }
            tempLeft++;
        }
        if (left < 0) {
            System.err.printf("%s没有包含%s的最小子串%n", s, t);
            return "";
        }
        int right = left -1;
        // minLen
        int minLen = Integer.MAX_VALUE;
        int leftIdx = -1;
        while (right < s.length()) {
            right++;
            if (right < s.length()) {
                char c = s.charAt(right);
                Integer cCount = needs.get(c);
                if (cCount != null) {
                    Integer cCountOfWindow = window.get(c);
                    window.put(c, cCountOfWindow + 1);
                }
            }

            if (valid(needs, window)) {
                minLen = Math.min(minLen, right - left + 1);
                if (minLen == right - left + 1) {
                    leftIdx = left;
                }
                while (valid(needs, window)) {
                    minLen = Math.min(minLen, right - left + 1);
                    if (minLen == right - left + 1) {
                        leftIdx = left;
                    }
                    char c1 = s.charAt(left);
                    if (window.containsKey(c1)) {
                        window.put(c1, window.get(c1) - 1);
                    }
                }
                while (!needs.containsKey(s.charAt(left)) && left <= right) {
                    left++;
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(leftIdx, minLen + leftIdx);
    }

    /**
     * 判断 window 是否符合 needs
     * @param needs
     * @param window
     * @return
     */
    private static boolean valid(Map<Character, Integer> needs, Map<Character, Integer> window) {
        for (Character character : needs.keySet()) {
            Integer count = window.get(character);
            Integer v = needs.get(character);
            if (count == null || count < v) {
                return false;
            }
        }
        return true;
    }
}
